package com.testing.class9;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int a[]=new int[]{4,2,9,5,1,3,8,4,5};
        int[] result=quickSort(a,0,8);
        System.out.println(Arrays.toString(result));

    }

    //每次递归调用的时候，需要指定要排序的下标范围，也就是low到high
    public static int[] quickSort(int[] a,int low,int high){
         //1、选一个基准值。比如选择最左边left。
        //2、需要两个指针，一个从左往右走left，一个从右往左走right。
        int left=low;
        int right=high;
        int base = a[left];

        //5、循环往复地进行从右往左的遍历和从左往右的遍历之间的交换，直到，left=right的时候，结束循环。
        while(left<right){
            //3、由于基准值在最左边，所以首先从右往左进行遍历。  都需要满足条件 left<right
            while(left<right){
                //判断：
                //	如果right的数比基准值大，那么不做操作，right--。

                if(a[right]>=base){
                    right--;
                }
                //	如果right的数比基准值小，那么进行交换。 并且改变遍历方向，变成从左往右遍历。left++。因为交换完之后，原本left的值就是比基准值小的，不用再比了。
                else{
                    int tmp=a[right];
                    //基准值在left的位置上。
                    a[right]=a[left];
                    a[left]=tmp;
                    //left++
                    left++;
                    //切换遍历方向，由break控制。
                    break;
                }
            }
            //4、从左往右的遍历
            while (left < right) {
//                判断：
//                如果left的数比基准值小，不做操作，left++。
//                如果left的数比基准值大，那么进行交换。并且改变遍历方向，变成从右往左遍历。同时right--.
//                基准值所在的位置，变成了left。
                if(a[left]<=base){
                    left++;
                }
                else{
                    int tmp=a[left];
                    a[left]=a[right];
                    a[right]=tmp;
                    //right--
                    right--;
                    //跳出从左往右的遍历，如果还满足left<right，就继续循环，进入从右往左的遍历。
                    break;
                }
            }

        }//结束一轮的完整遍历，基准值已经到了它正确的位置，left=right，基准值所在位置，既是left也是right。

        //递归调用的出口：
        //6、判断一下是否到达了递归出口，也就是，基准值左边和右边是否还需要排序。
        //				左边是否还有超过一个数：
        //					left-1>low的时候，继续调用递归(排左边剩下的数)。
        //				右边是否还有超过一个数：
        //					right+1<high的时候，继续调用递归(排右边剩下的数)。
        //排序左边
        if(left-1>low){
            //还没有排序的左边的范围就是  low到left-1
            quickSort(a,low,left-1);
        }else{
            //递归出口，就是不排序了。
        }

        //排序右边
        if(right+1<high){
            quickSort(a,right+1,high);
        }

        return a;
    }

}
